package com.yulongtian.weekCompetition.month202211.week4;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author yulongTian
 * @create 2022-11-27 11:17
 */
public class Test04 {
    public static void main(String[] args) {
        int[] nums = {5, 19, 11, 15, 13, 16, 4, 6, 2, 7, 10, 8, 18, 20, 1, 3, 17, 9, 12, 14};
        System.out.println(countSubarrays(nums, 6));
    }

    public static int countSubarrays(int[] nums, int k) {
        if (nums.length == 1) {
            return 1;
        }
        //定位在nums中的位置
        int kIndex = 0;
        int n = nums.length;
        while (nums[kIndex] != k) ++kIndex;
        HashMap<Integer, Integer> cnt = new HashMap<>();
        cnt.put(0, 1);

        for (int i = kIndex+1, c = 0; i < n; ++i) {
            c += nums[i] > k ? 1 : -1;
            cnt.put(c, cnt.getOrDefault(c, 0) + 1);
        }
        int res = cnt.get(0) + cnt.getOrDefault(1, 0);
        for (int i = kIndex - 1, c = 0; i >= 0; i--) {
            c += nums[i] < k ? 1 : -1;
            res += cnt.getOrDefault(c, 0) + cnt.getOrDefault(c + 1, 0);
        }
        return res;
    }

}
